一、KNN算法基本思想
K近邻算法,即KNN算法,可用于分类。该算法的基本思想非常简单:给定带标签的训练样本集,对于测试样本,根据事先设定的距离度量计算测试样本与每一个训练样本的距离,选出K个距离最近的训练样本,然后基于投票的方式将测试样本标记为k个训练样本中出现次数最多的类别。
KNN算法在训练阶段不产生模型,仅仅是将样本保存起来,训练的时间开销为零,是懒惰学习的典型代表。
二、KNN算法调优策略
距离度量的选择
选择合适的距离度量很重要,常用的距离有欧式距离、曼哈顿距离等。此后会有详细的距离度量的文章。
k的选择
k的选择非常重要。以下图为例,不同的k,分类结果会有显著的差别。
以二分类为例,图中蓝色加号代表正类,紫色减号代表负类,橙色三角形是待判样本。取k=3时,待判样本被标记为正类,取k=11时,待判样本被标识为负类,取k=15时,待判样本被标记为正类。
一般情况下,我们可将样本分为训练集和测试集,多尝试几组k值,通过测试样本的分类效果来确定合适的k值。
样本不平横问题
考虑如下情况。
以上图为例,针对这种样本不平衡的情况,很容易就会将测试样本标识为正类。我们可对负类样本进行重采用,对正类样本进行欠采样,其实本质就是调整样本权重。
三、优缺点分析
KNN算法简单有效,对数据的分布没有要求,训练阶段仅是保存数据,时间开销为零。由于KNN算法不产生模型,它在发现特征之间的关系上的能力有限,另外就是分类阶段很慢,因为该算法需要计算测试样本与每一个训练样本的距离,需要大量的内存,而且名义变量要额外处理。